package com.java.comprehensive.arithmetic.leecode.medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: 窦绍飞
 * @Date: 2022/8/4
 */
public class LeetCode_39 {

	List<List<Integer>> result = new ArrayList<>();
	List<Integer> list = new ArrayList<>();

	public List<List<Integer>> combinationSum(int[] candidates, int target) {
		Arrays.sort(candidates);
		backtracking(candidates, 0, target, 0);
		return result;
	}

	public void backtracking(int[] candidates, int start, int target, int sum) {
		if (sum > target) {
			return;
		} else if (sum == target) {
			result.add(new ArrayList<>(list));
			return;
		}
		for (int i = start; i < candidates.length && sum + candidates[i] <= target; i++) {
			list.add(candidates[i]);
			backtracking(candidates, i, target, sum + candidates[i]);
			list.remove(list.size() - 1);
		}
	}

	public static void main(String[] args) {
		int[] nums = {2, 7, 6, 3, 5, 1};
		LeetCode_39 leetCode_39 = new LeetCode_39();
		System.out.println(leetCode_39.combinationSum(nums, 9));
	}
}
